#include <stdlib.h>
#include <stdio.h>

typedef struct MyNode {
  int d;
  struct MyNode *left, *right;
} MyNode;

void initNode(MyNode* node) {
  if(node) {
    node->d = 0;
    node->left = NULL;
    node->right = NULL;
  };
};


#define QUEUE_MAX_LENGTH 100

typedef struct Queue {
  void *p[QUEUE_MAX_LENGTH];
  unsigned int last;
  unsigned int first;
} Queue;

void queueShift(Queue* q, unsigned int d) {
  for(unsigned int i=q->first; i>=q->last; i--) {
    q->p[i+d] = q->p[i];
  };

  q->last += d;
  q->first += d;
};

int queuePush(Queue* q, void* p) {
  if(q->last > 0) {
    q->last--;
    q->p[q->last] = p;
    return 1;
  } else {
    if(q->first < QUEUE_MAX_LENGTH-1) {
      queueShift(q, QUEUE_MAX_LENGTH-1 - q->first);
      q->last--;
      q->p[q->last] = p;
      return 1;
    };
  };
  return 0;
};

void queuePop(Queue* q) {
  q->first--;
};

void queueInit(Queue* q) {
  q->first = QUEUE_MAX_LENGTH-1;
  q->last = q->first+1;
};

void* queueFirst(Queue* q) {
  return q->last > q->first ? NULL : q->p[q->first];
};

void treeLevelTraversal(MyNode* node) {
  if(!node) return;

  Queue q;
  Queue* hq = &q;
  queueInit(hq);

  queuePush(hq, node);
  while(hq->last <= hq->first) {
    MyNode* hn = queueFirst(hq);
    queuePop(hq);
    printf("%d\n", hn->d);
    if(hn->left) queuePush(hq, hn->left);
    if(hn->right) queuePush(hq, hn->right);
  };

};

#define MAX_TABS 255
int count_of_tabs = 0;
char tabs_buf[MAX_TABS];

void pushTab() {
  if(count_of_tabs >= MAX_TABS) return;
  tabs_buf[count_of_tabs] = '\t';
  count_of_tabs++;
  tabs_buf[count_of_tabs] = '\0';
};

void popTab() {
  if(count_of_tabs <= 0) return;
  count_of_tabs--;
  tabs_buf[count_of_tabs] = '\0';
};

void treeTraversal(MyNode* node) {
  if(!node) return;
  pushTab();
  treeTraversal(node->right);
  printf("%s%d\n", tabs_buf, node->d);
  treeTraversal(node->left);
  popTab();
};

void treePush(MyNode* node, MyNode* el) {
  if(!node) return;

  Queue q;
  Queue* hq = &q;
  queueInit(hq);

  queuePush(hq, node);

  while(hq->last <= hq->first) {
    MyNode* hn = queueFirst(hq);
    queuePop(hq);

    if(hn->left) {
      queuePush(hq, hn->left);
    } else {
      hn->left = el;
      return;
    };

    if(hn->right) {
      queuePush(hq, hn->right);
    } else {
      hn->right = el;
      return;
    };
  };

};

MyNode* treeFind(MyNode* root, int d) {
  if(!root) return NULL;
  if(root->d == d) return root;
  MyNode* el;
  if(el = treeFind(root->left, d)) return el;
  if(el = treeFind(root->right, d)) return el;
  return NULL;
};

MyNode* treeDelete(MyNode* root, int d) {
  if(!root) return NULL;
  MyNode* el = treeFind(root, d);
  if(!el) return root;

  Queue q;
  Queue* hq = &q;
  queueInit(hq);

  MyNode* last_el;
  queuePush(hq, root);

  while(hq->last <= hq->first) {
    last_el = queueFirst(hq);
    queuePop(hq);

    if(last_el->left && (last_el->left->left || last_el->left->right))
      queuePush(hq, last_el->left);

    if(last_el->right && (last_el->right->left || last_el->right->right))
      queuePush(hq, last_el->right);
  };

  if(last_el->left) {
    el->d = last_el->left->d;
    last_el->left = NULL;
    return root;
  };

  if(last_el->right) {
    el->d = last_el->right->d;
    last_el->right = NULL;
    return root;
  };

  return NULL;

};

int main() {
  const int NODES_COUNT = 7;
  MyNode n[NODES_COUNT];
  for(int i=0; i<NODES_COUNT; i++) {
    initNode(&n[i]);
    n[i].d = i;
  };

  n[0].left = &n[1];
  n[0].right = &n[2];
  n[1].left = &n[3];
  n[1].right = &n[4];
  n[2].left = &n[5];
  n[2].right = &n[6];

  treeTraversal(&n[0]);

  printf("\n-----------\n");

  treeLevelTraversal(&n[0]);

  printf("\n\n");

  MyNode new_nodes[NODES_COUNT];
  for(int i=0; i < NODES_COUNT; i++) {
    initNode(&new_nodes[i]);
    new_nodes[i].d = i + NODES_COUNT;
    treePush(&n[0], &new_nodes[i]);
  };

  treeLevelTraversal(&n[0]);
  printf("\n\n");

  treeTraversal(&n[0]);

  if(treeFind(&n[0], 30)) printf("30 found\n");
  if(treeFind(&n[0], 13)) printf("13 found\n");

  MyNode* root = &n[0];

  int ans = 1;
  while(ans >= 0) {
    printf("node to delete: ");
    scanf("%d", &ans);
    root = treeDelete(root, ans);
    printf("\n------------\n");
    treeTraversal(root);
    printf("\n------------\n");
  };

  return 0;
};
